package sort

func BubbleSort(array []int32, orderBy OrderByEnum) {
	size := len(array)
	fn := orderBy.GetCompareFunc()
	for i := 0; i < size-1; i++ {
		for j := i + 1; j < size; j++ {
			if fn(array[i], array[j]) {
				array[i], array[j] = array[j], array[i]
			}
		}
	}
}

func SelectSort(array []int32, orderBy OrderByEnum) {
	size := len(array)
	fn := orderBy.GetCompareFunc()

	for i := 0; i < size-1; i++ {
		curIdx := i
		for j := i + 1; j < size; j++ {
			if fn(array[curIdx], array[j]) {
				temp := j
				j = curIdx
				curIdx = temp
			}
		}
		if curIdx != i {
			temp := array[curIdx]
			array[curIdx] = array[i]
			array[i] = temp
		}
	}
}

func InsertSort(array []int32, orderBy OrderByEnum) {
	size := len(array)
	fn := orderBy.GetCompareFunc()

	for i := 1; i < size; i++ {
		curIdx := i
		for j := curIdx - 1; j >= 0; j-- {
			if !fn(array[curIdx], array[j]) {
				temp := array[curIdx]
				array[curIdx] = array[j]
				array[j] = temp
				curIdx = j
				continue
			}
			break
		}
	}
}

func QuickSort(array []int32, orderBy OrderByEnum) {
	size := len(array)

	fn := orderBy.GetCompareFunc()
	quickSort(array, 0, size-1, fn)
}

func HeapSort(array []int32, orderBy OrderByEnum) {
	size := len(array)
	fn := orderBy.GetCompareFunc()
	// 循环建立初始堆
	for i := size / 2; i >= 0; i-- {
		heapAdjust(array, i, size, fn)
	}

	// 进行n-1次循环，完成排序
	for i := size - 1; i > 0; i-- {
		// 最后一个元素和第一元素进行交换
		array[i], array[0] = array[0], array[i]

		// 筛选 R[0] 结点，得到i-1个结点的堆
		heapAdjust(array, 0, i, fn)
	}
}

func MergeSort(array []int32, orderBy OrderByEnum) {
	fn := orderBy.GetCompareFunc()
	sortArray := mergeSort(array, fn)
	for i, v := range sortArray {
		array[i] = v
	}
}

func mergeSort(arr []int32, fn func(i, j int32) bool) []int32 {
	size := len(arr)
	if size < 2 {
		return arr
	}

	midIdx := size / 2
	left := arr[0:midIdx]
	right := arr[midIdx:]
	return merge(mergeSort(left, fn), mergeSort(right, fn), fn)
}

func merge(left, right []int32, fn func(i, j int32) bool) []int32 {
	var (
		leftIdx   int
		rightIdx  int
		leftSize  = len(left)
		rightSize = len(right)
		result    = make([]int32, 0)
	)

	for leftIdx < leftSize && rightIdx < rightSize {
		if fn(right[rightIdx], left[leftIdx]) {
			result = append(result, left[leftIdx])
			leftIdx++
			continue
		}
		result = append(result, right[rightIdx])
		rightIdx++
	}

	for leftIdx < leftSize {
		result = append(result, left[leftIdx])
		leftIdx++
	}
	for rightIdx < rightSize {
		result = append(result, right[rightIdx])
		rightIdx++
	}

	return result
}

func heapAdjust(arr []int32, parentIdx int, size int, fn func(i, j int32) bool) {
	var (
		rootVal  = arr[parentIdx]
		childIdx = 2*parentIdx + 1
	)
	for childIdx < size {
		rightChildIdx := childIdx + 1
		if rightChildIdx < size && fn(arr[rightChildIdx], arr[childIdx]) {
			childIdx = rightChildIdx
		}

		if fn(rootVal, arr[childIdx]) {
			break
		}
		// 子 -> 父
		arr[parentIdx] = arr[childIdx]
		// 继续检查子节点是否满足条件
		parentIdx = childIdx
		childIdx = 2*parentIdx + 1
	}
	// 父 -> 子
	arr[parentIdx] = rootVal
}

func quickSort(array []int32, low, high int, fn func(i, j int32) bool) {
	if low < high {
		i := low
		j := high
		x := array[i]

		for i < j {
			// 从右边开始找第一个"小于fn" x的数
			for i < j && fn(array[j], x) {
				j--
			}

			// 从左边开始找第一个"大于" x的数
			for i < j && fn(x, array[i]) {
				i++
			}
			if i < j {
				array[j], array[i] = array[i], array[j]
			}
		}
		array[i] = x
		quickSort(array, low, i-1, fn)
		quickSort(array, i+1, high, fn)
	}
}
